package de.haw.gka.a1;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.Set;

import org.jgrapht.graph.AbstractGraph;
import org.jgrapht.graph.DefaultWeightedEdge;
import org.jgrapht.graph.WeightedPseudograph;
import org.jgrapht.traverse.DepthFirstIterator;

public class AlgoFleury extends AbstractSearchAlgo {

	private AbstractGraph<Knoten, DefaultWeightedEdge> graph= new WeightedPseudograph<Knoten, DefaultWeightedEdge>(DefaultWeightedEdge.class);
	private List<Knoten> knotenWeg = new ArrayList<Knoten>();
	private List<DefaultWeightedEdge> kantenWeg= new  ArrayList<DefaultWeightedEdge>();
	
	
	public AlgoFleury(AbstractGraph<Knoten, DefaultWeightedEdge> graph){
            for(Knoten k: graph.vertexSet()){
                this.graph.addVertex(k);
            }
            for(DefaultWeightedEdge e:graph.edgeSet()){
                Knoten von = graph.getEdgeSource(e);
                Knoten zu = graph.getEdgeTarget(e);
                this.graph.addEdge(von, zu, e);
            }
            algo();

    }
	
	
	private void algo(){

		//Radom ersten Knoten waehlen
		List<Knoten> zwischenList= new ArrayList<Knoten>(graph.vertexSet());
		Random generator = new Random();
		int random = generator.nextInt(graph.vertexSet().size());
		Knoten current=zwischenList.get(random);
				
		DefaultWeightedEdge zuLoeschen= null;
		int hinundher=0;
		//ersten Knoten hinzufügen
		knotenWeg.add(current);
		//solange bis keine kante mehr im graphen
		while(!graph.edgeSet().isEmpty()){
            //löscht zwischenlist
			zwischenList.clear();
			//nimmt ersten Nachbarn
			Knoten nachbar=nachbarKnoten(current).get(0);
			//richtige Kante nehmen
			if(graph.containsEdge(current, nachbar)){
				zuLoeschen= graph.getEdge(current, nachbar);
				hinundher=1;
			}
			else{
				zuLoeschen= graph.getEdge(nachbar, current);
				hinundher=0;
			}
			
			//wenn letzte Kante
			if(graph.edgeSet().size()<2){
                //löscht kante
				graph.removeEdge(zuLoeschen);
				knotenWeg.add(nachbar);
				kantenWeg.add(zuLoeschen);
			}
			else{
				//Kante loeschen
				graph.removeEdge(zuLoeschen);
			
				//dfs
				DepthFirstIterator<Knoten, DefaultWeightedEdge> dfsIter = new DepthFirstIterator<Knoten, DefaultWeightedEdge>(graph, nachbar);
			    //füllt zwischenlist

				while(dfsIter.hasNext()){
					Knoten tmp= dfsIter.next();
					zwischenList.add(tmp);
				}
				//wenn dfs(zwischenlist) ausganzpunkt enth�lt oder ausganzpunkt keine Kanten mehr hat
				if(zwischenList.contains(current)||knotenGrad(current)==0){
					knotenWeg.add(nachbar);
					kantenWeg.add(zuLoeschen);
					current= nachbar;
				}
				else{
                        //wenn kante brückenkante war kante wieder zum graphen hinzufügen
						if(hinundher==1){
							graph.addEdge(current, nachbar, zuLoeschen);
						}
						else{
							graph.addEdge(nachbar, current, zuLoeschen);
						}
				}
			}
		}

	}
	
	private int knotenGrad(Knoten k){
		Set<DefaultWeightedEdge> zwischen = graph.edgesOf(k);
		return zwischen.size();
	}
	
	private List<Knoten> nachbarKnoten(Knoten knoten){
		List<Knoten> nachbarList= new ArrayList<Knoten>();
		 //durchlaeuft alle kanten eines knoten
		for(DefaultWeightedEdge edge : graph.edgesOf(knoten)){	
			Knoten neighbor = graph.getEdgeSource(edge);
            //den richtigen knoten bekommen
			if(neighbor.equals(knoten)){
				neighbor=graph.getEdgeTarget(edge);
			}
	       	nachbarList.add(neighbor); 
		}
		return nachbarList;
	}
	
	@Override
	public List getTheShortestWay() {	
		return kantenWeg;
	}
	public List getWay(){
		return knotenWeg;
	}
}
